package com.sinaapp.gavinzhang.Eleven;

import org.junit.Test;

/**
 * Created by gavin on 15-8-12.
 */
public class Sort {

    public void InsertSort()
    {//插入排序
        int[] tmp = {9,8,7,6,5,4,3,2,1,0};

        for (int i = 1; i < tmp.length; i++) {
            int t = tmp[i];
            for (int j = i; j >0 ; j--) {
                if (tmp[j] < tmp[j-1])
                {
                    tmp[j] ^=tmp[j-1];
                    tmp[j-1] ^= tmp[j];
                    tmp[j] ^=tmp[j-1];

                }else {
                    tmp[j] = t;
                    break;
                }
            }
        }
        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i]+"  ");
        }
    }


    public void ShellSort()
    {//希尔排序
        int[] tmp = {9,8,7,6,5,4,3,2,1,0};
        for (int d = tmp.length/2;d!=0; d /=2)
        {
            for (int i = d; i < tmp.length; i += d) {
                int t = tmp[i];
                for (int j = i; j >0 ; j -= d) {
                    if (tmp[j] < tmp[j-d])
                    {
                        tmp[j] ^=tmp[j-d];
                        tmp[j-d] ^= tmp[j];
                        tmp[j] ^=tmp[j-d];

                    }else {
                        tmp[j] = t;
                        break;
                    }
                }
            }
        }

        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i]+"  ");
        }
    }


    @Test
    public void BubbleSort()
    {//冒泡排序
        int[] tmp = {9,8,7,6,5,4,3,2,1,0};

        for (int i = 0; i < tmp.length; i++) {
            for (int j = 0; j < tmp.length-i-1; j++) {
                if (tmp[j] > tmp[j+1])
                {
                    tmp[j] ^= tmp[j+1];
                    tmp[j+1] ^= tmp[j];
                    tmp[j] ^= tmp[j+1];
                }
            }
        }

        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i]+"  ");
        }
    }

    @Test
    public void SampleSort()
    {//选择排序
        //int[] tmp = {0,1,2,3,4,6,5,7,8,9};
        int[] tmp = {9,8,7,6,5,4,3,2,1,0};
        for (int i = 0; i < tmp.length-1; i++) {
            for (int j = i+1; j < tmp.length; j++) {
                if (tmp[j] < tmp[i])
                {
                    tmp[j] ^= tmp[i];
                    tmp[i] ^= tmp[j];
                    tmp[j] ^= tmp[i];
                }
            }
        }

        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i]+"  ");
        }
    }



    @Test
    public void quickSearchTest()
    {//快速排序测试
        //int[] tmp = {5,6,4,7,9,8,3,1,2};
        int[] tmp = {9,8,7,6,5,4,3,2,1};
        quickSort(tmp,0,tmp.length-1);
        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i]+"  ");
        }

    }

    public void quickSort(int[] tmp,int low,int upper)
    {//快速排序
        if (low>=upper)return;

        int t = tmp[low];
        int start = low;
        int stop = upper;
        while (start < stop)
        {
            while (start<stop && tmp[stop] > t)--stop;
            if (start < stop)
            {
                tmp[start++] = tmp[stop];
            }
            while (start<stop && tmp[start] < t)++start;
            if (start < stop)
            {
                tmp[stop--] = tmp[start];
            }
        }

        tmp[start] = t;
        quickSort(tmp,low,start-1);
        quickSort(tmp,start+1,upper);

    }
}
